package z_test;

/**
 * 要求：求一个字符串的最长重复子串
 * 思路：使用两个指针，两个指针的间隔从1，2，3...依次增大， 同时向右移动两个指针，在移动的过程中判断指针位置的字符是否相同，并记录最长子串的长度。
 * @author Y
 *
 */
public class Solution {
	
	// 求解字符串中的最长重复子串
	public static String maxRepat(String str){
		//参数检查
		if (str == null || str.length() == 0) {
			return "字符串为空!";
		}
		// 重复子串的最长长度
		int max = 0;
		// 最长重复子串的起始位置
		int first = 0;
		int k = 0;
		for (int i = 1; i < str.length(); i++) {
			for (int j = 0; j < str.length() - i; j++) {
				if (str.charAt(i) == str.charAt(i+j)) {
					k++;
				} else {
					k = 0;
				}
				if (k > max) {
					max = k;
					first = j - k + 1;
				}
			}
		}
		
		if (max > 0 ) {
			System.out.println(max);
			return str.substring(first, first + max);
		}
		
		return null;
	}
	
	
	public static void main(String[] args) {
		String s = "abcd123abcd123";
		String s1 = "asadfffffggghhj";
		System.out.println(Solution.maxRepat(s));
		System.out.println(Solution.maxRepat(s1));
		
	}
	
	
	
}
